/*
 * @lc app=leetcode.cn id=240 lang=cpp
 *
 * [240] 搜索二维矩阵 II
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    int m;
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        m = matrix.size();
        return search(matrix, target, 0, matrix[0].size()-1);

        // lower_bound这玩意是二分查找？？？
        // 不是binary_search这个么。。。
        // for (const auto& row: matrix) {
        //     auto it = lower_bound(row.begin(), row.end(), target);
        //     if (it != row.end() && *it == target) {
        //         return true;
        //     }
        // }

    }
    bool search(const vector<vector<int>>& matrix, int target,
                int roll, int column){
        if (matrix[roll][column] == target){
            return true;
        }
        // too large, go left
        if (matrix[roll][column] > target and column != 0){
            return search(matrix, target, roll, column-1);
        }
        // too small, go down
        if (matrix[roll][column] < target and roll != m-1){
            return search(matrix, target, roll+1, column);
        }
        return false;
    }
};
// @lc code=end

